LeetCode——字符串相乘

NO.43 字符串相乘中等

思路一：竖式法 想一想竖式是怎么一步一步进行的，模拟这个过程。两个步骤：

逆序(从低位向高位)遍历乘数num2的每个元素，依次与num1相乘。这个过程中需要注意除了num2的第一个元素(个位数)其他元素都需要在低位补充相应数量的0。每次相乘的结果temp是逆序的。
将num2的每个元素与num1相乘得到的结果temp和ans相加，此时是顺序遍历两个参数。

遍历结束之后返回逆序结果的翻转。

public String multiply(String num1, String num2) {
    if (num1==null||num2==null||num1.equals("0")||num2.equals("0")||num1.equals("")||num2.equals(""))return "0";
    StringBuilder ans=new StringBuilder();
    //遍历num2的每个元素
    for (int i=0;i<num2.length();i++){
        int x = num2.charAt(num2.length()-i-1)-'0',carry=0;
        StringBuilder temp=new StringBuilder();
        //除了第一次个位数，其他位需要在低位补相应数量的0
        for (int k=0;k<i;k++)temp.append(0);
        //依次与num1的每个元素相乘
        for (int j=0;j<num1.length();j++){
            int y = num1.charAt(num1.length()-j-1)-'0';
            //注意加上进位值
            int sum=x*y+carry;
            carry=sum/10;
            temp.append(sum%10);
        }
        //注意检查进位值，不要遗漏
        if (carry>0)temp.append(carry);
        //将每位上的乘法结果和ans相加
        ans=sum(ans,temp);
    }
    //最后需要将ans翻转，变成正确顺序
    return ans.reverse().toString();
}
//将两个字符串相加
private StringBuilder sum(StringBuilder num1, StringBuilder num2) {
    StringBuilder ans=new StringBuilder();
    int carry=0,len=Math.max(num1.length(),num2.length());
    for (int i=0;i<len;i++){
        //两个字符串长度不相等的时候，短的那个在高位补0
        int x=i<num1.length()?num1.charAt(i)-'0':0;
        int y=i<num2.length()?num2.charAt(i)-'0':0;
        //注意加上进位
        int sum=x+y+carry;
        carry=sum/10;
        ans.append(sum%10);
    }
    //循环结束也要检查进位，防止遗漏
    if (carry>0)ans.append(carry);
    return ans;
}

时间复杂度：O(MN)

思路二：优化竖式法 该算法是通过两数相乘时，乘数某位与被乘数某位相乘，与产生结果的位置的规律来完成。具体规律如下：

乘数 num1 位数为 MM，被乘数 num2 位数为 NN， num1 x num2 结果 res 最大总位数为 M+N。
num1[i] x num2[j] 的结果为 tmp(位数为两位，”0x”,”xy”的形式)，其第一位位于 res[i+j]，第二位位于 res[i+j+1]。

public String multiply(String num1, String num2) {
        if (num1==null||num2==null||num1.equals("0")||num2.equals("0")||num1.equals("")||num2.equals(""))return "0";
        //两数相乘积最多为M+N位
        int[] res=new int[num1.length()+num2.length()];
        for (int i=num1.length()-1;i>=0;i--){
            int x = num1.charAt(i) - '0';
            for (int j=num2.length()-1;j>=0;j--){
                int y = num2.charAt(j) - '0';
                int sum=x*y+res[i+j+1];
                res[i+j+1]=sum%10;
                res[i+j]+=sum/10;
            }
        }
        StringBuilder ans=new StringBuilder();
        for (int i = 0; i < res.length; i++) {
            //积的最高位可能为零，省去不要
            if (i==0&&res[0]==0)continue;
            ans.append(res[i]);
        }
        return ans.toString();
    }

时间复杂度:O(MN)

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github

NO.43 字符串相乘 中等

NO.43 字符串相乘中等